#include <iostream>
#include <string.h>
using namespace std;

#include "tabbporo.h"
#include "tcolaabbporo.h"

/** \file tabbporo.cpp
* \brief Procedimientos de la clase tabbporo.
*
* STANISLAV LITVINENKO DNI:02062226T
* JOSE FRANCES IRIONDO DNI:48469642V
*/

TNodoABB::TNodoABB(const TNodoABB &nodo)
{
    item=nodo.item;
    iz=nodo.iz;
    de=nodo.de;
}
TNodoABB::~TNodoABB()
{

}

TNodoABB & TNodoABB::operator=(const TNodoABB &nodo)
{
    if(this!=&nodo)
    {
        item=nodo.item;
        iz=nodo.iz;
        de=nodo.de;
    }
}

//=============================FIN DE TNODOABB==============================

TABBPoro::TABBPoro(const TABBPoro &poro)
{
    if(poro.nodo!=NULL)
    {
        nodo = new TNodoABB(*poro.nodo);
    }
    else
    {
        nodo = NULL;
    }
}

TABBPoro::~TABBPoro()
{
    if(nodo!=NULL)
    {
        delete nodo;
    }
    nodo = NULL;
}

TABBPoro & TABBPoro::operator=(const TABBPoro &aaa)
{
	if(this!=&aaa)
	{
		this->~TABBPoro();
		if(aaa.nodo!=NULL)
		{
			nodo=new TNodoABB;
			*nodo=*(aaa.nodo);
		}
	}
	return *this;
}
bool TABBPoro::operator==(const TABBPoro &de) const
{
	bool igual=false;


        TVectorPoro a;
        TVectorPoro b;

        a=this->Inorden();
        b=de.Inorden();

        if(a==b)
        {
            igual=true;
        }
       /* cout << nodo->item<<endl;
        cout << de.nodo->item<<endl;
	if(nodo==NULL && de.nodo==NULL)
		igual=true;
	else if(nodo==NULL && de.nodo!=NULL)
		igual=false;
	else if(nodo!=NULL && de.nodo==NULL)
		igual=false;
	else if(nodo->item==de.nodo->item && nodo->iz==de.nodo->iz && nodo->de==de.nodo->de)
		igual=true;
	else
		igual=false;*/

	return igual;
}

bool TABBPoro::EsVacio() const
{
	bool vacia;

	if(nodo==NULL)
		vacia=true;
	else
		vacia=false;

	return vacia;
}

bool TABBPoro::Insertar(const TPoro &p)
{
    bool insertado;

    if(!Buscar(p))
    {
        if(nodo==NULL)
        {
            nodo=new TNodoABB;
            nodo->item=p;
            insertado=true;
        }
        else if(nodo->item.Volumen()==p.Volumen())
        {
            insertado=false;
        }
        else
        {
            //cout <<  "Poro a insertar:"<< p.Volumen() << endl;
            //cout << "Poro que hay:"<< nodo->item.Volumen() << endl;
            if(p.Volumen()<nodo->item.Volumen())
                    insertado=nodo->iz.Insertar(p);
            else
                    insertado=nodo->de.Insertar(p);
        }
    }

    return insertado;
}

bool TABBPoro::Borrar(const TPoro &p)
{
        TNodoABB *pB;
	bool borrado;
	TABBPoro mayorIzquierda;
        TPoro mayor;

	if(nodo == NULL)	//El Poro no se encuentra en el arbol.
		borrado=false;
	else
	{
		if(p.Volumen() < nodo->item.Volumen())
		{
			borrado=nodo->iz.Borrar(p);
		}
		else
		{
                    
			if(p.Volumen() > nodo->item.Volumen())
				borrado=nodo->de.Borrar(p);
                        else if(strcmp(p.Color(),nodo->item.Color())==0)	//El Poro se ha encontrado en el arbol.
			{
				borrado=true;
				//Los 4 tipos distintos de borrado.
				//Primer caso borrar(Nodo hoja). Los hijos a null.
				if(nodo->iz.nodo==NULL && nodo->de.nodo==NULL)
				{
					delete nodo;
					nodo=NULL;
				}
				//Segundo caso borrar (derecha null e izquierda no.
				else if(nodo->de.nodo==NULL && nodo->iz.nodo!=NULL)
				{
					pB=nodo;
					nodo=pB->iz.nodo;
					pB->iz.nodo=NULL;
					delete pB;
				}
				//Tercer caso de borrar (izquierda null y derecha no.
				else if(nodo->de.nodo!=NULL && nodo->iz.nodo==NULL)
				{
					pB=nodo;
					nodo=pB->de.nodo;
					pB->de.nodo=NULL;
					delete pB;
				}
				//Cuarto caso de borrar (tiene dos hijos).
				else
                                {
					mayor=nodo->iz.BuscarMayor();
					nodo->item=mayor;
					nodo->iz.Borrar(mayor);
				}
			}
		}
	}
	return borrado;
}

TPoro TABBPoro::BuscarMayor() const
{
	TPoro p;
	TNodoABB *pNodo=NULL;

	pNodo=nodo;
	while(pNodo->de.nodo!=NULL)
	{
		pNodo=pNodo->de.nodo;
	}
	p=pNodo->item;
	return p;
}

bool TABBPoro::Buscar(const TPoro &p) const
{
	bool enc;

	if(nodo==NULL)
		enc=false;
        else if(p.Volumen()==nodo->item.Volumen() && strcmp(p.Color(),nodo->item.Color())==0)
		enc=true;
	else if(p.Volumen() < nodo->item.Volumen())
		enc=nodo->iz.Buscar(p);
	else
		enc=nodo->de.Buscar(p);
	return enc;
}

TPoro TABBPoro::Raiz() const
{
	TPoro raiz;

	if(nodo)
		raiz=nodo->item;

	return raiz;
}

int TABBPoro::Altura() const
{
	int alt=0, altIz, altDe;

	if(nodo==NULL)
        {
		alt=0;
        }
        else
	{
		altIz=nodo->iz.Altura();
		altDe=nodo->de.Altura();

		if(altIz>altDe)
			alt=1+altIz;
		else
			alt=1+altDe;
	}

	return alt;
}

int TABBPoro::Nodos() const
{
	int n=0;

        if(nodo!=NULL)
        {
            
		n=nodo->iz.Nodos()+nodo->de.Nodos();
                n=n+1;
        }
        else
        {
            n=0;
        }

	return n;
}

int TABBPoro::NodosHoja() const
{
	int nh;

	if(nodo==NULL)
        {
		nh=0;
        }
	else if(nodo->iz.nodo==NULL && nodo->de.nodo ==NULL)
        {
			nh=1;
        }
	else
        {
		nh=nodo->iz.NodosHoja() + nodo->de.NodosHoja();
        }

	return nh;
}

TABBPoro TABBPoro::operator+(const TABBPoro &aaa) const
{
	TABBPoro aux(*this);
	TVectorPoro vectPoro;
	int posicion, tam;
        
	vectPoro=aaa.Niveles();
	tam=vectPoro.Longitud();

	for(posicion=1;posicion<=tam;posicion++)
		aux.Insertar(vectPoro[posicion]);
 
	return aux;
}

TABBPoro TABBPoro::operator-(TABBPoro &aaa) const
{
	TABBPoro aux(*this);
	TVectorPoro vectPoro;
	int posicion, tam;

	vectPoro=aaa.Niveles();
	tam=vectPoro.Longitud();

	for(posicion=1;posicion<=tam;posicion++)
		aux.Borrar(vectPoro[posicion]);
	return aux;
}

// Devuelve el recorrido en inorden
TVectorPoro TABBPoro::Inorden() const
{
  // Posición en el vector que almacena el recorrido
       int posicion = 1;
  // Vector del tamaño adecuado para almacenar todos los nodos
       TVectorPoro v(Nodos());
       InordenAux(v, posicion);
       return v;
}

// Devuelve el recorrido en inorden
TVectorPoro TABBPoro::Preorden() const
{
  // Posición en el vector que almacena el recorrido
       int posicion = 1;
  // Vector del tamaño adecuado para almacenar todos los nodos
       TVectorPoro v(Nodos());
       PreordenAux(v, posicion);
       return v;
}

// Devuelve el recorrido en inorden
TVectorPoro TABBPoro::Postorden() const
{
  // Posición en el vector que almacena el recorrido
       int posicion = 1;
  // Vector del tamaño adecuado para almacenar todos los nodos
       TVectorPoro v(Nodos());
       PostordenAux(v, posicion);
       return v;
}

void TABBPoro::InordenAux(TVectorPoro &UP, int &pos) const
{
	if(nodo!=NULL)
	{
		nodo->iz.InordenAux(UP,pos);
		UP[pos]=nodo->item;
		pos++;
		nodo->de.InordenAux(UP,pos);
	}
}

void TABBPoro::PreordenAux(TVectorPoro &UP, int &pos) const
{
	if(nodo!=NULL)
	{
		UP[pos]=nodo->item;
		pos++;
		nodo->iz.PreordenAux(UP,pos);
		nodo->de.PreordenAux(UP,pos);
	}
}

void TABBPoro::PostordenAux(TVectorPoro &UP, int &pos) const
{
	if(nodo!=NULL)
	{
		nodo->iz.PostordenAux(UP,pos);
		nodo->de.PostordenAux(UP,pos);
		UP[pos]=nodo->item;
		pos++;
	}
}

TVectorPoro TABBPoro::Niveles() const
{
        TVectorPoro niveles(Nodos());
	TColaABBPoro cola;
	//TABBPoro *aux;
        TABBPoro *aux;
	int posicion=0;

        if(!this->EsVacio())
        {
            cola.Encolar((TABBPoro*) this);
        }


  while(!cola.EsVacia())
  {
   aux=cola.Cabeza(); //aux sera la cabeza de la cola
   cola.Desencolar(); //desencolamos la cabeza
   posicion++;
   
   niveles[posicion]=aux->Raiz();
   
   //niveles.dimension=posicion;
   
   
   
   if(!aux->nodo->iz.EsVacio()) //si el hijo izquierdo no esta vacio
   {
                         TABBPoro* hijoIz = new TABBPoro(aux->nodo->iz);
                        cola.Encolar(hijoIz);
   }
   if(!aux->nodo->de.EsVacio()) //si el hijo derecho no esta vacio
   {
                           TABBPoro* hijoDe = new TABBPoro(aux->nodo->de);
                        cola.Encolar(hijoDe);
   }
  }

	return niveles;
}
ostream & operator<<(ostream &os, const TABBPoro &arbol)
{
    TVectorPoro vectorp;

    vectorp=arbol.Niveles();

    os << vectorp;


    return os;
}
//========================FIN DE TABBPORO========================


